// Copyright 2015 the V8 project authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

#ifndef V8_COMPILER_BYTECODE_GRAPH_BUILDER_H_
#define V8_COMPILER_BYTECODE_GRAPH_BUILDER_H_

#include "src/compiler/bytecode-analysis.h"
#include "src/compiler/js-graph.h"
#include "src/compiler/js-type-hint-lowering.h"
#include "src/compiler/state-values-utils.h"
#include "src/interpreter/bytecode-array-iterator.h"
#include "src/interpreter/bytecode-flags.h"
#include "src/interpreter/bytecodes.h"
#include "src/source-position-table.h"

namespace v8 {
namespace internal {

    class VectorSlotPair;

    namespace compiler {

        class Reduction;
        class SourcePositionTable;

        // The BytecodeGraphBuilder produces a high-level IR graph based on
        // interpreter bytecodes.
        class BytecodeGraphBuilder {
        public:
            BytecodeGraphBuilder(
                Zone* local_zone, Handle<BytecodeArray> bytecode_array,
                Handle<SharedFunctionInfo> shared, Handle<FeedbackVector> feedback_vector,
                BailoutId osr_offset, JSGraph* jsgraph,
                CallFrequency& invocation_frequency,
                SourcePositionTable* source_positions, Handle<Context> native_context,
                int inlining_id = SourcePosition::kNotInlined,
                JSTypeHintLowering::Flags flags = JSTypeHintLowering::kNoFlags,
                bool stack_check = true, bool analyze_environment_liveness = true);

            // Creates a graph by visiting bytecodes.
            void CreateGraph();

        private:
            class Environment;
            class OsrIteratorState;
            struct SubEnvironment;

            void RemoveMergeEnvironmentsBeforeOffset(int limit_offset);
            void AdvanceToOsrEntryAndPeelLoops(
                interpreter::BytecodeArrayIterator* iterator,
                SourcePositionTableIterator* source_position_iterator);

            void VisitSingleBytecode(
                SourcePositionTableIterator* source_position_iterator);
            void VisitBytecodes();

            // Get or create the node that represents the outer function closure.
            Node* GetFunctionClosure();

            // Builder for loading the a native context field.
            Node* BuildLoadNativeContextField(int index);

            // Helper function for creating a pair containing type feedback vector and
            // a feedback slot.
            VectorSlotPair CreateVectorSlotPair(int slot_id);

            void set_environment(Environment* env) { environment_ = env; }
            const Environment* environment() const { return environment_; }
            Environment* environment() { return environment_; }

            // Node creation helpers
            Node* NewNode(const Operator* op, bool incomplete = false)
            {
                return MakeNode(op, 0, static_cast<Node**>(nullptr), incomplete);
            }

            Node* NewNode(const Operator* op, Node* n1)
            {
                Node* buffer[] = { n1 };
                return MakeNode(op, arraysize(buffer), buffer, false);
            }

            Node* NewNode(const Operator* op, Node* n1, Node* n2)
            {
                Node* buffer[] = { n1, n2 };
                return MakeNode(op, arraysize(buffer), buffer, false);
            }

            Node* NewNode(const Operator* op, Node* n1, Node* n2, Node* n3)
            {
                Node* buffer[] = { n1, n2, n3 };
                return MakeNode(op, arraysize(buffer), buffer, false);
            }

            Node* NewNode(const Operator* op, Node* n1, Node* n2, Node* n3, Node* n4)
            {
                Node* buffer[] = { n1, n2, n3, n4 };
                return MakeNode(op, arraysize(buffer), buffer, false);
            }

            Node* NewNode(const Operator* op, Node* n1, Node* n2, Node* n3, Node* n4,
                Node* n5, Node* n6)
            {
                Node* buffer[] = { n1, n2, n3, n4, n5, n6 };
                return MakeNode(op, arraysize(buffer), buffer, false);
            }

            // Helpers to create new control nodes.
            Node* NewIfTrue() { return NewNode(common()->IfTrue()); }
            Node* NewIfFalse() { return NewNode(common()->IfFalse()); }
            Node* NewIfValue(int32_t value) { return NewNode(common()->IfValue(value)); }
            Node* NewIfDefault() { return NewNode(common()->IfDefault()); }
            Node* NewMerge() { return NewNode(common()->Merge(1), true); }
            Node* NewLoop() { return NewNode(common()->Loop(1), true); }
            Node* NewBranch(Node* condition, BranchHint hint = BranchHint::kNone,
                IsSafetyCheck is_safety_check = IsSafetyCheck::kSafetyCheck)
            {
                return NewNode(common()->Branch(hint, is_safety_check), condition);
            }
            Node* NewSwitch(Node* condition, int control_output_count)
            {
                return NewNode(common()->Switch(control_output_count), condition);
            }

            // Creates a new Phi node having {count} input values.
            Node* NewPhi(int count, Node* input, Node* control);
            Node* NewEffectPhi(int count, Node* input, Node* control);

            // Helpers for merging control, effect or value dependencies.
            Node* MergeControl(Node* control, Node* other);
            Node* MergeEffect(Node* effect, Node* other_effect, Node* control);
            Node* MergeValue(Node* value, Node* other_value, Node* control);

            // The main node creation chokepoint. Adds context, frame state, effect,
            // and control dependencies depending on the operator.
            Node* MakeNode(const Operator* op, int value_input_count,
                Node* const* value_inputs, bool incomplete);

            Node** EnsureInputBufferSize(int size);

            Node* const* GetCallArgumentsFromRegisters(Node* callee, Node* receiver,
                interpreter::Register first_arg,
                int arg_count);
            Node* const* ProcessCallVarArgs(ConvertReceiverMode receiver_mode,
                Node* callee, interpreter::Register first_reg,
                int arg_count);
            Node* ProcessCallArguments(const Operator* call_op, Node* const* args,
                int arg_count);
            Node* ProcessCallArguments(const Operator* call_op, Node* callee,
                interpreter::Register receiver, size_t reg_count);
            Node* const* GetConstructArgumentsFromRegister(
                Node* target, Node* new_target, interpreter::Register first_arg,
                int arg_count);
            Node* ProcessConstructArguments(const Operator* op, Node* const* args,
                int arg_count);
            Node* ProcessCallRuntimeArguments(const Operator* call_runtime_op,
                interpreter::Register receiver,
                size_t reg_count);

            // Prepare information for eager deoptimization. This information is carried
            // by dedicated {Checkpoint} nodes that are wired into the effect chain.
            // Conceptually this frame state is "before" a given operation.
            void PrepareEagerCheckpoint();

            // Prepare information for lazy deoptimization. This information is attached
            // to the given node and the output value produced by the node is combined.
            // Conceptually this frame state is "after" a given operation.
            void PrepareFrameState(Node* node, OutputFrameStateCombine combine);

            void BuildCreateArguments(CreateArgumentsType type);
            Node* BuildLoadGlobal(Handle<Name> name, uint32_t feedback_slot_index,
                TypeofMode typeof_mode);

            enum class StoreMode {
                // Check the prototype chain before storing.
                kNormal,
                // Store value to the receiver without checking the prototype chain.
                kOwn,
            };
            void BuildNamedStore(StoreMode store_mode);
            void BuildLdaLookupSlot(TypeofMode typeof_mode);
            void BuildLdaLookupContextSlot(TypeofMode typeof_mode);
            void BuildLdaLookupGlobalSlot(TypeofMode typeof_mode);
            void BuildCallVarArgs(ConvertReceiverMode receiver_mode);
            void BuildCall(ConvertReceiverMode receiver_mode, Node* const* args,
                size_t arg_count, int slot_id);
            void BuildCall(ConvertReceiverMode receiver_mode,
                std::initializer_list<Node*> args, int slot_id)
            {
                BuildCall(receiver_mode, args.begin(), args.size(), slot_id);
            }
            void BuildUnaryOp(const Operator* op);
            void BuildBinaryOp(const Operator* op);
            void BuildBinaryOpWithImmediate(const Operator* op);
            void BuildCompareOp(const Operator* op);
            void BuildDelete(LanguageMode language_mode);
            void BuildCastOperator(const Operator* op);
            void BuildHoleCheckAndThrow(Node* condition, Runtime::FunctionId runtime_id,
                Node* name = nullptr);

            // Optional early lowering to the simplified operator level.  Note that
            // the result has already been wired into the environment just like
            // any other invocation of {NewNode} would do.
            JSTypeHintLowering::LoweringResult TryBuildSimplifiedUnaryOp(
                const Operator* op, Node* operand, FeedbackSlot slot);
            JSTypeHintLowering::LoweringResult TryBuildSimplifiedBinaryOp(
                const Operator* op, Node* left, Node* right, FeedbackSlot slot);
            JSTypeHintLowering::LoweringResult TryBuildSimplifiedForInNext(
                Node* receiver, Node* cache_array, Node* cache_type, Node* index,
                FeedbackSlot slot);
            JSTypeHintLowering::LoweringResult TryBuildSimplifiedForInPrepare(
                Node* receiver, FeedbackSlot slot);
            JSTypeHintLowering::LoweringResult TryBuildSimplifiedToNumber(
                Node* input, FeedbackSlot slot);
            JSTypeHintLowering::LoweringResult TryBuildSimplifiedCall(const Operator* op,
                Node* const* args,
                int arg_count,
                FeedbackSlot slot);
            JSTypeHintLowering::LoweringResult TryBuildSimplifiedConstruct(
                const Operator* op, Node* const* args, int arg_count, FeedbackSlot slot);
            JSTypeHintLowering::LoweringResult TryBuildSimplifiedLoadNamed(
                const Operator* op, Node* receiver, FeedbackSlot slot);
            JSTypeHintLowering::LoweringResult TryBuildSimplifiedLoadKeyed(
                const Operator* op, Node* receiver, Node* key, FeedbackSlot slot);
            JSTypeHintLowering::LoweringResult TryBuildSimplifiedStoreNamed(
                const Operator* op, Node* receiver, Node* value, FeedbackSlot slot);
            JSTypeHintLowering::LoweringResult TryBuildSimplifiedStoreKeyed(
                const Operator* op, Node* receiver, Node* key, Node* value,
                FeedbackSlot slot);

            // Applies the given early reduction onto the current environment.
            void ApplyEarlyReduction(JSTypeHintLowering::LoweringResult reduction);

            // Check the context chain for extensions, for lookup fast paths.
            Environment* CheckContextExtensions(uint32_t depth);

            // Helper function to create binary operation hint from the recorded
            // type feedback.
            BinaryOperationHint GetBinaryOperationHint(int operand_index);

            // Helper function to create compare operation hint from the recorded
            // type feedback.
            CompareOperationHint GetCompareOperationHint();

            // Helper function to create for-in mode from the recorded type feedback.
            ForInMode GetForInMode(int operand_index);

            // Helper function to compute call frequency from the recorded type
            // feedback.
            CallFrequency ComputeCallFrequency(int slot_id) const;

            // Helper function to extract the speculation mode from the recorded type
            // feedback.
            SpeculationMode GetSpeculationMode(int slot_id) const;

            // Control flow plumbing.
            void BuildJump();
            void BuildJumpIf(Node* condition);
            void BuildJumpIfNot(Node* condition);
            void BuildJumpIfEqual(Node* comperand);
            void BuildJumpIfNotEqual(Node* comperand);
            void BuildJumpIfTrue();
            void BuildJumpIfFalse();
            void BuildJumpIfToBooleanTrue();
            void BuildJumpIfToBooleanFalse();
            void BuildJumpIfNotHole();
            void BuildJumpIfJSReceiver();

            void BuildSwitchOnSmi(Node* condition);
            void BuildSwitchOnGeneratorState(
                const ZoneVector<ResumeJumpTarget>& resume_jump_targets,
                bool allow_fallthrough_on_executing);

            // Simulates control flow by forward-propagating environments.
            void MergeIntoSuccessorEnvironment(int target_offset);
            void BuildLoopHeaderEnvironment(int current_offset);
            void SwitchToMergeEnvironment(int current_offset);

            // Simulates control flow that exits the function body.
            void MergeControlToLeaveFunction(Node* exit);

            // Builds loop exit nodes for every exited loop between the current bytecode
            // offset and {target_offset}.
            void BuildLoopExitsForBranch(int target_offset);
            void BuildLoopExitsForFunctionExit(const BytecodeLivenessState* liveness);
            void BuildLoopExitsUntilLoop(int loop_offset,
                const BytecodeLivenessState* liveness);

            // Helper for building a return (from an actual return or a suspend).
            void BuildReturn(const BytecodeLivenessState* liveness);

            // Simulates entry and exit of exception handlers.
            void ExitThenEnterExceptionHandlers(int current_offset);

            // Update the current position of the {SourcePositionTable} to that of the
            // bytecode at {offset}, if any.
            void UpdateSourcePosition(SourcePositionTableIterator* it, int offset);

            // Growth increment for the temporary buffer used to construct input lists to
            // new nodes.
            static const int kInputBufferSizeIncrement = 64;

            // An abstract representation for an exception handler that is being
            // entered and exited while the graph builder is iterating over the
            // underlying bytecode. The exception handlers within the bytecode are
            // well scoped, hence will form a stack during iteration.
            struct ExceptionHandler {
                int start_offset_; // Start offset of the handled area in the bytecode.
                int end_offset_; // End offset of the handled area in the bytecode.
                int handler_offset_; // Handler entry offset within the bytecode.
                int context_register_; // Index of register holding handler context.
            };

            // Field accessors
            Graph* graph() const { return jsgraph_->graph(); }
            CommonOperatorBuilder* common() const { return jsgraph_->common(); }
            Zone* graph_zone() const { return graph()->zone(); }
            JSGraph* jsgraph() const { return jsgraph_; }
            Isolate* isolate() const { return jsgraph_->isolate(); }
            JSOperatorBuilder* javascript() const { return jsgraph_->javascript(); }
            SimplifiedOperatorBuilder* simplified() const
            {
                return jsgraph_->simplified();
            }
            Zone* local_zone() const { return local_zone_; }
            const Handle<BytecodeArray>& bytecode_array() const
            {
                return bytecode_array_;
            }
            const Handle<FeedbackVector>& feedback_vector() const
            {
                return feedback_vector_;
            }
            const JSTypeHintLowering& type_hint_lowering() const
            {
                return type_hint_lowering_;
            }
            const FrameStateFunctionInfo* frame_state_function_info() const
            {
                return frame_state_function_info_;
            }

            const interpreter::BytecodeArrayIterator& bytecode_iterator() const
            {
                return *bytecode_iterator_;
            }

            void set_bytecode_iterator(
                interpreter::BytecodeArrayIterator* bytecode_iterator)
            {
                bytecode_iterator_ = bytecode_iterator;
            }

            const BytecodeAnalysis* bytecode_analysis() const
            {
                return bytecode_analysis_;
            }

            void set_bytecode_analysis(const BytecodeAnalysis* bytecode_analysis)
            {
                bytecode_analysis_ = bytecode_analysis;
            }

            int currently_peeled_loop_offset() const
            {
                return currently_peeled_loop_offset_;
            }

            void set_currently_peeled_loop_offset(int offset)
            {
                currently_peeled_loop_offset_ = offset;
            }

            bool stack_check() const { return stack_check_; }

            void set_stack_check(bool stack_check) { stack_check_ = stack_check; }

            bool analyze_environment_liveness() const
            {
                return analyze_environment_liveness_;
            }

            int current_exception_handler() { return current_exception_handler_; }

            void set_current_exception_handler(int index)
            {
                current_exception_handler_ = index;
            }

            bool needs_eager_checkpoint() const { return needs_eager_checkpoint_; }
            void mark_as_needing_eager_checkpoint(bool value)
            {
                needs_eager_checkpoint_ = value;
            }

            Handle<SharedFunctionInfo> shared_info() const { return shared_info_; }

            Handle<Context> native_context() const { return native_context_; }

#define DECLARE_VISIT_BYTECODE(name, ...) void Visit##name();
            BYTECODE_LIST(DECLARE_VISIT_BYTECODE)
#undef DECLARE_VISIT_BYTECODE

            Zone* local_zone_;
            JSGraph* jsgraph_;
            CallFrequency const invocation_frequency_;
            Handle<BytecodeArray> bytecode_array_;
            Handle<FeedbackVector> feedback_vector_;
            const JSTypeHintLowering type_hint_lowering_;
            const FrameStateFunctionInfo* frame_state_function_info_;
            const interpreter::BytecodeArrayIterator* bytecode_iterator_;
            const BytecodeAnalysis* bytecode_analysis_;
            Environment* environment_;
            BailoutId osr_offset_;
            int currently_peeled_loop_offset_;
            bool stack_check_;
            bool analyze_environment_liveness_;

            // Merge environments are snapshots of the environment at points where the
            // control flow merges. This models a forward data flow propagation of all
            // values from all predecessors of the merge in question. They are indexed by
            // the bytecode offset
            ZoneMap<int, Environment*> merge_environments_;

            // Generator merge environments are snapshots of the current resume
            // environment, tracing back through loop headers to the resume switch of a
            // generator. They allow us to model a single resume jump as several switch
            // statements across loop headers, keeping those loop headers reducible,
            // without having to merge the "executing" environments of the generator into
            // the "resuming" ones. They are indexed by the suspend id of the resume.
            ZoneMap<int, Environment*> generator_merge_environments_;

            // Exception handlers currently entered by the iteration.
            ZoneStack<ExceptionHandler> exception_handlers_;
            int current_exception_handler_;

            // Temporary storage for building node input lists.
            int input_buffer_size_;
            Node** input_buffer_;

            // Optimization to only create checkpoints when the current position in the
            // control-flow is not effect-dominated by another checkpoint already. All
            // operations that do not have observable side-effects can be re-evaluated.
            bool needs_eager_checkpoint_;

            // Nodes representing values in the activation record.
            SetOncePointer<Node> function_closure_;

            // Control nodes that exit the function body.
            ZoneVector<Node*> exit_controls_;

            StateValuesCache state_values_cache_;

            // The source position table, to be populated.
            SourcePositionTable* source_positions_;

            SourcePosition const start_position_;

            Handle<SharedFunctionInfo> const shared_info_;

            // The native context for which we optimize.
            Handle<Context> const native_context_;

            static int const kBinaryOperationHintIndex = 1;
            static int const kCountOperationHintIndex = 0;
            static int const kBinaryOperationSmiHintIndex = 1;
            static int const kUnaryOperationHintIndex = 0;

            DISALLOW_COPY_AND_ASSIGN(BytecodeGraphBuilder);
        };

    } // namespace compiler
} // namespace internal
} // namespace v8

#endif // V8_COMPILER_BYTECODE_GRAPH_BUILDER_H_
